﻿#include <iostream>
#include "Graph.h"

//     ---------      -----------
//   /          \    /           \
// /             ↘ /             ↘
// A------>B----->C----->D-------->E
//         \           ↗
//          \         /
//           ---------

static void topologySort(const Graph* graph, vector<GraphNode*>& sortedNodes)
{
    GraphNode* nodeInEqualsZero = nullptr;
    unordered_map<GraphNode*, int> remainInMap;
    for (auto nodePairIterator = graph->nodes.begin(); nodePairIterator != graph->nodes.end(); nodePairIterator++)
    {
        auto node = nodePairIterator->second;
        remainInMap.insert({ node, node->in });
        if (node->in == 0 && !nodeInEqualsZero)
        {
            nodeInEqualsZero = node;
        }
    }

    if (!nodeInEqualsZero) return;

    sortedNodes.push_back(nodeInEqualsZero);
    GraphNode* nextInZero = nullptr;
    while (sortedNodes.size() < graph->nodes.size())
    {
        for (auto nodeIterator = nodeInEqualsZero->nextNodes.begin(); nodeIterator != nodeInEqualsZero->nextNodes.end(); nodeIterator++)
        {
            auto next = *nodeIterator;
            auto nextIn = remainInMap[next];
            remainInMap[next] = nextIn - 1;
            if (nextIn == 1)
            {
                sortedNodes.push_back(next);
                nextInZero = next;
            }
        }

        nodeInEqualsZero = nextInZero;
    }
}

/**
 * 拓扑排序
 * 适用范围：有向图，且有入度为0的节点，且没有环
 *
 *     ---------      -----------
 *   /          \    /           \
 * /             ↘ /             ↘
 * A------>B----->C----->D-------->E
 *         \           ↗
 *          \         /
 *           ---------
 *
 * 依次将入度为0的点从图中去掉，其出向的边也去掉，并将这个点加入到List中
 * 上图拓扑排序：A->B->C->D->E
 *
 */
int main_TopologySort()
{
    int matrix[][3] = {
        {'a','b',1},
        {'a','c',1},
        {'b','c',1},
        {'b','d',1},
        {'c','d',1},
        {'c','e',1},
        {'d','e',1},
    };

    int* pMatrix = matrix[0];
    auto graph = Graph::generate(&pMatrix, sizeof(matrix) / sizeof(int) / 3, 3, true);
    vector<GraphNode*> sortedNodes;
    topologySort(graph, sortedNodes);

    for (auto nodeIterator = sortedNodes.begin(); nodeIterator != sortedNodes.end(); nodeIterator++)
    {
        printf("%c->", (*nodeIterator)->value);
    }

    printf("\n");

    return 0;
}